#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

int t, k;

ll qpow(ll a, ll p, ll m) {
    ll res = 1;
    a %= m;
    while (p) {
        if (p & 1) res = res * a % m;
        a = a * a % m;
        p >>= 1;
    }
    return res;
}
int phi(int n) {
    int ans = n;
    for (int p = 2;p * p <= n;p++)if (n % p == 0) {
        while (n % p == 0)n /= p;
        ans -= ans / p;
    }
    if (n != 1)ans -= ans / n;
    return ans;
}

vector<int> divisor(int n) {
    vector<int> div;
    for (int d = 1;d * d <= n;d++)if (n % d == 0) {
        div.push_back(d);
        if (d != n / d)div.push_back(n / d);
    }
    sort(div.begin(), div.end());
    return div;
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> k;

        ll m = (k & 1) ? k * 9 : k * 9 / 2;

        int res = -1;
        for (int i : divisor(phi(m))) {
            if (qpow(10, i, m) == 1) {
                res = i;
                break;
            }
        }
        cout << res << endl;
    }
    return 0;
}